package com.cty.B_SpecialDataStructures.B_Queue.QueueChain;

import com.cty.F_common.DataItem;

/**
 * @Auther: cty
 * @Date: 2020/6/14 9:05
 * @Description: 双端链表（双端单向）
 * 重要操作：
 *      ① insertFirst(DataItem): void    O(1)
 *      ② deleteFirst(): DataItem    O(1)
 *      ③ insertLast(DataItem): void    O(1)
 *
 *      删除尾端需要知道尾端节点需要用到previous，单向链表无法实现
 *      ②③组合创建 链表实现栈
 * @version: 1.0
 */
class FirstLastList {
    private Node first;
    private Node last;

    public FirstLastList(){
        first = null;
        last = null;
    }

    public Node getFirst(){
        return first;
    }

    public boolean isEmpty(){
        return (first == null);
    }

    public void displayList(){
        Node current = first;
        while(current != null){
            System.out.print(current.data.getKey() + " ");
            current = current.next;
        }
        System.out.println();
    }

    /**
     * 在表头插入    O(1)
     * @param item
     */
    public void insertFirst(DataItem item){
        Node newNode = new Node(item);
        if(isEmpty())  // 空表插入，需要考虑last
            last = newNode;
        newNode.next = first;
        first = newNode;
    }  // end insertFirst()

    /**
     * 在表头删除    O(1)
     * @return
     */
    public DataItem deleteFirst(){
        if(isEmpty())
            return null;

        DataItem temp = first.data;
        first = first.next;
        if(first == null)  // 若删除后变空表，需要考虑last
            last = null;
        return temp;
    }  // end deleteFirst()

    /**
     * 在表尾插入    O(1)
     * @param item
     */
    public void insertLast(DataItem item){
        Node newNode = new Node(item);

        if(isEmpty()){  // 空表插入，需要考虑first并单独作为一种情况
            first = newNode;
            last = newNode;
            return;
        }

        last.next = newNode;
        last = newNode;
    }  // end insertLast()

}  // end FirstLastList{}
